Вершинно-транзитивный граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов вершинно-транзитивным графом называется граф G такой, что для любых двух вершин v1 и v2 графа G существует автоморфизм

такой, что

Другими словами, граф вершинно-транзитивен, если его группа автоморфизма действует транзитивно относительно вершин[1]. Граф вершинно-транзитивен тогда и только тогда, когда результаты автоморфизмов его дополнения идентичны.

Любой симметричный граф без изолированных вершин является вершинно-транзитивным, и любой вершинно-транзитивный граф является регулярным. Однако не все вершинно-транзитивные графы симметричны (например, рёбра усечённого тетраэдра), и не все регулярные графы вершинно-транзитивны (например, граф Фрухта и граф Титце).

Примеры конечных графов

[править | править код]
Рёбра усечённого тетраэдра формируют вершинно-транзитивный граф (одновременно и граф Кэли), не являющийся симметричным.

Множество конечных вершинно-транзитивных графов включает симметричные графы (такие как граф Петерсена, граф Хивуда и вершины и рёбра правильных многогранников). Конечные графы Кэли (такие как соединённые в куб циклы) являются вершинно-транзитивными, как и вершины и рёбра архимедова тела (хотя только 2 из них симметричны). Поточник, Спига и Веррет (Potočnik, Spiga, Verret) создали перепись всех связных кубических (то есть с вершинами степени 3) вершинно-транзитивных графов с числом вершин, не превышающим 1280[2].

Рёберная связность вершинно-транзитивного графа равна степени d, в то время как вершинная связность будет как минимум 2(d+1)/3[3]. Если степень равна 4 или меньше, или граф также рёберно транзитивен, или граф является минимальным графом Кэли, то вершинная связность будет равна d[4].

Примеры бесконечных графов

[править | править код]

Бесконечные вершинно-транзитивные графы включают:

Два счётных вершинно-транзитивных графа называются квазиизометричными[англ.], если отношение их функций расстояния ограничено снизу и сверху. Хорошо известная гипотеза утверждяет, что любой бесконечный вершинно-транзитивный граф квазиизоморфен графу Кэли. Контрпример был представлен Рейнхардом Дистелем (Reinhard Diestel) и Имре Лидером (Imre Leader) в 2001-м году[5]. В 2005-м году Эскин, Фишер и Вайт (Eskin, Fisher, Whyte) подтвердили верность контрпримера[6].

Примечания

[править | править код]
  1. Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — Т. 207.
  2. Potočnik P., Spiga P. and Verret G. (2012), Cubic vertex-transitive graphs on up to 1280 vertices, Journal of Symbolic Computation{{citation}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Википедия:Обслуживание CS1 (числовые имена: authors list) (ссылка)
  3. Godsil, C. and Royle, G. Algebraic Graph Theory. — Springer Verlag, 2001.
  4. Babai, L. Technical Report TR-94-10. — University of Chicago, 1996.アーカイブされたコピー. Дата обращения: 29 августа 2010. Архивировано 11 июня 2010 года.
  5. Reinhard Diestel, Imre Leader. A conjecture concerning a limit of non-Cayley graphs // Journal of Algebraic Combinatorics. — 2001. — Т. 14, вып. 1. — С. 17–25. — doi:10.1023/A:1011257718029.
  6. Alex Eskin, David Fisher, Kevin Whyte. Quasi-isometries and rigidity of solvable groups. — 2005.